package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/'>节点与其祖先之间的最大差值(Maximum Difference Between Node and Ancestor)</a>
 * <p>给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
 *      输出：7
 *      解释：
 *          我们有大量的节点与其祖先的差值，其中一些如下：
 *          |8 - 3| = 5
 *          |3 - 7| = 4
 *          |8 - 1| = 7
 *          |10 - 13| = 3
 * 在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
 *
 * 示例 2：
 *      输入：root = [1,null,2,null,0,3]
 *      输出：3
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>树中的节点数在 2 到 5000 之间。</li>
 *      <li>0 <= Node.val <= 10^5</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/22 14:35
 */
public class LC1026MaximumDifferenceBetweenNodeAndAncestor_M {
    static class Solution {

        public int maxAncestorDiff(TreeNode root) {
            return dfs(root, root.val, root.val);
        }

        /**
         * 过程
         *
         * @param currNode             当前节点
         * @param ancestorNodeMinValue 所有祖先节点的最小值
         * @param ancestorNodeMaxValue 所有祖先节点的最大值
         */
        private int dfs(TreeNode currNode, int ancestorNodeMinValue, int ancestorNodeMaxValue) {
            if (currNode == null) {
                return 0;
            }
            int diff = Math.max(Math.abs(currNode.val - ancestorNodeMinValue), Math.abs(currNode.val - ancestorNodeMaxValue));
            ancestorNodeMinValue = Math.min(ancestorNodeMinValue, currNode.val);
            ancestorNodeMaxValue = Math.max(ancestorNodeMaxValue, currNode.val);
            diff = Math.max(diff, dfs(currNode.left, ancestorNodeMinValue, ancestorNodeMaxValue));
            diff = Math.max(diff, dfs(currNode.right, ancestorNodeMinValue, ancestorNodeMaxValue));
            return diff;
        }


        public int maxAncestorDiff2(TreeNode root) {
            int maxDiff = 0;
            Map<TreeNode, TreeNode> parentNodeMap = new HashMap<>();
            buildParentNodeMap(root, parentNodeMap);
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode currNode = queue.poll();
                TreeNode parentNode = parentNodeMap.get(currNode);
                while (parentNode != null) {
                    maxDiff = Math.max(maxDiff, Math.abs(parentNode.val - currNode.val));
                    parentNode = parentNodeMap.get(parentNode);
                }
                if (currNode.left != null) {
                    queue.offer(currNode.left);
                }
                if (currNode.right != null) {
                    queue.offer(currNode.right);
                }
            }
            return maxDiff;
        }

        private void buildParentNodeMap(TreeNode currNode, Map<TreeNode, TreeNode> parentNodeMap) {
            if (currNode == null) {
                return;
            }
            if (currNode.left != null) {
                parentNodeMap.put(currNode.left, currNode);
                buildParentNodeMap(currNode.left, parentNodeMap);
            }
            if (currNode.right != null) {
                parentNodeMap.put(currNode.right, currNode);
                buildParentNodeMap(currNode.right, parentNodeMap);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(8);
        root1.left = new TreeNode(3);
        root1.left.left = new TreeNode(1);
        root1.left.right = new TreeNode(6);
        root1.left.right.left = new TreeNode(4);
        root1.left.right.right = new TreeNode(7);
        root1.right = new TreeNode(10);
        root1.right.right = new TreeNode(14);
        root1.right.right.left = new TreeNode(13);

        TreeNode root2 = new TreeNode(1);
        root2.right = new TreeNode(2);
        root2.right.right = new TreeNode(0);
        root2.right.right.left = new TreeNode(3);

        Solution solution = new Solution();
        System.out.println(solution.maxAncestorDiff(root1));
        System.out.println(solution.maxAncestorDiff(root2));
    }
}
